#ifndef MGRAPH_H
#define MGRAPH_H
#include <stdio.h>
#include <stdlib.h>
#include "../util/Queue.h"

typedef int WeightType;
typedef char DataType; // 此数据结构仅供存储数据类型为char的图使用，如有其他用途请根据联动更改，联动标识↓
typedef int Vertex;
typedef int bool;
#define INFINITY INT_MAX  // 最大值为char的最大值↓
#define MAXVerticesNum 100 // 最大顶点数

/* 图结点的定义 */
typedef struct GNode *PtrToGNode;
struct GNode
{
    int Nv; // Number of vertices
    int Ne; // Number of edges
    WeightType G[MAXVerticesNum][MAXVerticesNum];
    DataType Data[MAXVerticesNum];
};
typedef PtrToGNode MGraph;

/* 边的定义 */
typedef struct ENode *PtrToENode;
struct ENode
{
    Vertex v1, v2;
    WeightType weight;
};
typedef PtrToENode Edge;

MGraph CreateGraph(int VerticesNum);

void InsertEdge(MGraph M, Edge E);

// Input version
MGraph BuildGraph();

/* 无权图单源最短路 T = O(|V| + |E|) */
// void Unweighted(Vertex S);

// 找到最小路径
Vertex FindMinDist(MGraph Graph, int dist[], int collected[]);

// 有权图的单源最短路算法，输入图，dist数组，path数组，源点S
bool Dijkstra(MGraph Graph, int dist[], int path[], Vertex S);

MGraph CreateGraph(int VerticesNum)
{
    Vertex V, W;
    MGraph M;

    M = (MGraph)malloc(sizeof(struct GNode));
    M->Nv = VerticesNum;
    M->Ne = 0;

    // The default index starts from 0 to (M->Ne - 1)
    for (V = 0; V < M->Nv; V++)
    {
        for (W = 0; W < M->Nv; W++)
        {
            M->G[V][W] = INFINITY; // can be 0 in unweighted graph or infinite and
        }
    }
    return M;
}

void InsertEdge(MGraph Graph, Edge E)
{
    Graph->G[E->v1][E->v2] = E->weight;

    // If the graph is an undirected graph
    Graph->G[E->v2][E->v1] = E->weight;
}

MGraph BuildGraph()
{
    MGraph Graph;
    Edge E;
    Vertex V;
    int Nv;

    scanf("%d ", &Nv);           /* 读入顶点个数 */
    Graph = CreateGraph(Nv);     /* 初始化有Nv个顶点但没有边的图 */
    scanf("%d", &(Graph->Ne)); /* 读入边数 */

    if (Graph->Ne != 0) // 如果有边
    {
        E = (Edge)malloc(sizeof(Edge)); // 新建一个边节点

        // 读入边，输入格式“尾（起点） 头（终点） 权重”，然后插入邻接矩阵
        for (int i = 0; i < Graph->Ne; i++)
        {
            scanf("%d %d %d", &E->v1, &E->v2, &E->weight);
            InsertEdge(Graph, E);
        }
    }

    /* 如果顶点有数据的话，读入数据 */
    for (V = 0; V < Graph->Nv; V++)
        scanf("%c", &(Graph->Data[V])); // ↓

    return Graph;
}

Vertex FindMinDist(MGraph Graph, int dist[], int collected[])
{
    Vertex V, MinV;
    int MinDist = INFINITY;

    for (V = 0; V < Graph->Nv; V++)
    {
        /* 如果顶点V没有被收录，且存在一个距离dist[V]小于之前计算出的最小距离，
        就把最小距离MinDist更新为dist[V]，最小距离顶点序号MinV更新为V */
        if (collected[V] == 0 && dist[V] < MinDist)
        {
            MinDist = dist[V];
            MinV = V;
        }
    }

    /* 如果最小距离MinDist小于正无穷，就返回最小距离顶点序号MinV；
    否则，说明不存在通路，返回错误顶点序号-1 */
    if (MinDist < INFINITY)
        return MinV;
    else
        return -1;
}

bool Dijkstra(MGraph Graph, int dist[], int path[], Vertex S)
{
    bool collected[MAXVerticesNum];
    Vertex V, W;

    // 利用源点S初始化dist, collected和path
    for (V = 0; V < Graph->Nv; V++)
    {
        dist[V] = Graph->G[S][V];
        if (dist[V] != INFINITY)
            path[V] = S;
        else
            path[V] = -1;
        collected[V] = 0;
    }

    // 初始化完成后，将源点加入dist
    dist[S] = 0; // 其实可以不用写？
    collected[S] = 1;

    while (1)
    {
        /* 找出最小距离顶点（序号）V，若得到错误序号-1，说明图不连通，退出循环 */
        V = FindMinDist(Graph, dist, collected);
        if (V == -1)
        {
            break;
        }
        collected[V] = 1;

        // 对于 V 的每个邻接点 W， 如果W还没被收录，且经过 V 到 W 的距离小于当前 W 的距离且不为无穷大，就更新 W 的dist和path
        //注意要无负边，有负边就要返回错误
        for (W = 0; W < Graph->Nv; W++)
        {
            if (!collected[W] && Graph->G[V][W] < INFINITY)
            {
                if (Graph->G[V][W] < 0)
                {
                    return 0;
                }
                
                if (dist[V] + Graph->G[V][W] < dist[W])
                {
                    dist[W] = dist[V] + Graph->G[V][W];
                    path[W] = path[V];
                }
            }
        }
    }

    return 1;
}

#endif // MGRAPH_H
